package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.list.singly.ListNode;
import leetcode.editor.cn.util.list.singly.ListUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

/**
 * 没想到好的办法，还是看了答案
 * 这里需要把 head 提出来，如果每次都传的话指针会出问题
 *
 * @author qidi
 * @date 2022-01-06 13:44:10
 */
class Q0109_ConvertSortedListToBinarySearchTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        ListNode globalNode;

        public TreeNode sortedListToBST(ListNode head) {
            globalNode = head;
            int size = 0;
            while (head != null) {
                size++;
                head = head.next;
            }

            TreeNode process = process(0, size);
            return process;
        }

        private TreeNode process(int l, int r) {
            if (l >= r) return null;

            int mid = (r + l) / 2;

            TreeNode root = new TreeNode();
            // 构建左树
            root.left = process(l, mid);
            // 正好 node 来到了中点
            root.val = globalNode.val;
            globalNode = globalNode.next;
            // 构建右树
            root.right = process(mid + 1, r);

            return root;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0109_ConvertSortedListToBinarySearchTree().new Solution();
        solution.sortedListToBST(ListUtil.getInstance().generateFromArray(-10, -3, 0, 5, 9));
    }
}